package dp;

//将一个字符串转换为另一个字符串时最少的步骤
public class EditString {

	public static void main(String[] args) {
		System.out.println(minDistance("a", "b"));
	}
	
	//注意这里之所以没有用i表示下标，是因为只有一个值得时候，使用下标会出现-1，就没有用了
	//dp[i][j]表示长度为i（o--->i -1)和长度为j(0---> j -1)变换相等所需要的步数
	//dp[i][j] = dp[i - 1][j - 1] (if string1[i] == string2[j])
	//dp[i][j] = min(replace, delete, insert)
	//replace = dp[i - 1][j - 1] + 1 
	//delete = dp[i - 1][j] + 1//直接将string1[i - 1]删除，然后去匹配i - 2 与j
	//insert = dp[i][j - 1] + 1 // 将string2[j]中的字符插入到s1中i - 1之后
	//接下来就只需要匹配string1[i - 1] 与  string2[j - 2];
	//比如 abcd  abm  插入之后就变成了 abcdm ， abm 由于最后m想等，于是就成了 abcd ，ab
    public static int minDistance(String word1, String word2) {
    	int length1 = word1.length();
    	int length2 = word2.length();
    	char[] string1 = word1.toCharArray();
    	char[] string2 = word2.toCharArray();
    	if(length1 == 0 || length2 == 0){
    		return length1 == 0 ? length2 : length1;
    	}
    	int[][] result = new int[length1 + 1][length2 + 1];
    	for (int i = 0; i < result.length; i++) {
			result[i][0] = i;  //初始条件，将0 --> i 的字符串变为 长度为0 需要i步
		}
    	for (int j = 0; j < result[0].length; j++) {
			result[0][j] = j;  //初始条件，将0 --> j 的字符串变为 长度为0 需要j步
		}
    	for (int i = 1; i < result.length; i++) {
			for (int j = 1; j < result[0].length; j++) {
				if(string1[i - 1] == string2[j - 1]){
					result[i][j] = result[i - 1][j - 1];
				}else {
					result[i][j] = getMin(result[i - 1][j - 1] + 1, result[i - 1][j] + 1, 
							result[i][j - 1] + 1);
				}
			}
		}
    	for (int j = 0; j < result[0].length; j++) {
    		for (int i = 0; i < result.length; i++) 
				System.out.print(" " + result[i][j]);
			System.out.println();
		}
    	System.out.println(result[length1][length2]);
        return result[length1][length2];
    }
    
    public static int getMin(int a, int b, int c){
    	return Math.min(a, Math.min(b, c));
    }
}
